home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 1.iso / desktop / winmaze4.zip / HEXMAZE.CPP < prev    next >
C/C++ Source or Header  |  1994-05-02  |  49KB  |  1,248 lines
  1. #include <owl\owlpch.h>
  2. #include <owl\applicat.h>
  3. #include <owl\framewin.h>
  4. #include <owl\dc.h>
  5. #include <stdlib.h>
  6. #include "oracle.h"
  7. #include "cell.h"
  8. #include "hexmaze.h"
  9.  
  10. #ifndef TRUE
  11. #define TRUE -1
  12. #endif
  13. #ifndef FALSE
  14. #define FALSE 0
  15. #endif
  16.  
  17. typedef cell *cell_ptr;
  18. typedef char *char_ptr;
  19.  
  20. hexmaze::hexmaze(int row_count,int column_count,int thickness_of_wall,
  21.   char *seed,TFrameWindow *win_ptr)
  22. //      Contruct a maze having "row_count" rows and "column_count" columns of
  23. // rooms.  The walls should be "thickness_of_wall" (bricks) thick.  A different
  24. // (8 character of less) "seed" generally yields a different maze.
  25.   {
  26.     struct
  27.       {
  28.          int row_num;
  29.          int column_num;
  30.       }  delta [2] [6];
  31.     int  mud_filled_room_found;
  32.     struct
  33.       {
  34.          int row_num;
  35.          int column_num;
  36.       }  next;
  37.     char wall [720] [6];
  38.     char wall_to_check;
  39.     char wall_num;
  40.     char way_out;
  41.     int  x1;
  42.     int  x2;
  43.     int  y1;
  44.     int  y2;
  45.  
  46. unlink("HEXMAZE.LOG");
  47.     window_ptr=win_ptr; 
  48.     wall_thickness=thickness_of_wall;
  49.     num_rows=row_count;
  50.     num_y_dots=wall_thickness*(4*num_rows+1);
  51.     y_dot_max=num_y_dots-1;
  52.     num_columns=column_count;
  53.     max_x=8*(num_columns/2)+6;
  54.     num_x_dots=wall_thickness*(max_x+1);
  55.     x_dot_max=num_x_dots-1;
  56.     // Allocate a two dimensional array of rooms.
  57.     if (memory_allocated=((room=new cell_ptr[num_rows]) != NULL))
  58.       {
  59.               int row_num=0;
  60.         while (memory_allocated && (row_num < num_rows))
  61.           if (memory_allocated=((room[row_num]=new cell [num_columns]) != NULL))
  62.             row_num++;
  63.         if (! memory_allocated)
  64.           {
  65.             while (row_num)
  66.               delete [] room[--row_num];
  67.             delete [] room;
  68.             window_ptr->MessageBox("Cannot allocate maze!",
  69.              window_ptr->GetApplication()->GetName(),
  70.              MB_OK | MB_ICONEXCLAMATION);
  71.           }
  72.       }
  73.     if (memory_allocated)
  74.       {
  75.          // Allocate a two dimensional array for plotting the maze in
  76.          // terms of "bricks" where a wall is "wall_thickness" bricks
  77.          // thick.
  78.          if (memory_allocated=((page=new char_ptr [num_y_dots]) != NULL))
  79.            {
  80.              int y_dot_num=0;
  81.              while (memory_allocated && (y_dot_num < num_y_dots))
  82.                if (memory_allocated=((page[y_dot_num]=new char [num_x_dots])
  83.                 != NULL))
  84.                  y_dot_num++;
  85.              if (! memory_allocated)
  86.                {
  87.                   while (y_dot_num)
  88.                     delete [] page[--y_dot_num];
  89.                   delete [] page;
  90.                   for (int row_num=num_rows-1; row_num >= 0; row_num--)
  91.                     delete [] room[row_num];
  92.                   delete [] room;
  93.                   window_ptr->MessageBox("Cannot allocate maze!",
  94.                    window_ptr->GetApplication()->GetName(),
  95.                    MB_OK | MB_ICONEXCLAMATION);
  96.                }
  97.            }
  98.          else
  99.            {
  100.               for (int row_num=num_rows-1; row_num >= 0; row_num--)
  101.                 delete [] room[row_num];
  102.               delete [] room;
  103.               window_ptr->MessageBox("Cannot allocate maze!",
  104.                window_ptr->GetApplication()->GetName(),
  105.                MB_OK | MB_ICONEXCLAMATION);
  106.            }
  107.       }
  108.     if (memory_allocated)
  109.       {
  110.          // Set up the directions by which a room can be exited.
  111.          // Directions for even columns.
  112.          delta[0][0].row_num=-1;    // north
  113.          delta[0][0].column_num=0;
  114.          delta[0][1].row_num=-1;    // northwest
  115.          delta[0][1].column_num=-1;
  116.          delta[0][2].row_num=0;     // southwest
  117.          delta[0][2].column_num=-1;
  118.          delta[0][3].row_num=1;     // south
  119.          delta[0][3].column_num=0;
  120.          delta[0][4].row_num=0;     // southeast
  121.          delta[0][4].column_num=1;
  122.          delta[0][5].row_num=-1;    // northeast
  123.          delta[0][5].column_num=1;
  124.          // Directions for odd columns.
  125.          delta[1][0].row_num=-1;    // north
  126.          delta[1][0].column_num=0;
  127.          delta[1][1].row_num=0;     // northwest
  128.          delta[1][1].column_num=-1;
  129.          delta[1][2].row_num=1;     // southwest
  130.          delta[1][2].column_num=-1;
  131.          delta[1][3].row_num=1;     // south
  132.          delta[1][3].column_num=0;
  133.          delta[1][4].row_num=1;     // southeast
  134.          delta[1][4].column_num=1;
  135.          delta[1][5].row_num=0;     // northeast
  136.          delta[1][5].column_num=1;
  137.          // Set up the 6! orders in which the wall of a room can be accessed.
  138.          int order_num=0;
  139.          for (int wall_num_1=0; wall_num_1 < 6; wall_num_1++)
  140.            for (int wall_num_2=0; wall_num_2 < 6; wall_num_2++)
  141.              if (wall_num_2 != wall_num_1)
  142.                for (int wall_num_3=0; wall_num_3 < 6; wall_num_3++)
  143.                  if ((wall_num_3 != wall_num_2)
  144.                  &&  (wall_num_3 != wall_num_1))
  145.                    for (int wall_num_4=0; wall_num_4 < 6; wall_num_4++)
  146.                      if ((wall_num_4 != wall_num_3)
  147.                      &&  (wall_num_4 != wall_num_2)
  148.                      &&  (wall_num_4 != wall_num_1))
  149.                        for (int wall_num_5=0; wall_num_5 < 6; wall_num_5++)
  150.                          if ((wall_num_5 != wall_num_4)
  151.                          &&  (wall_num_5 != wall_num_3)
  152.                          &&  (wall_num_5 != wall_num_2)
  153.                          &&  (wall_num_5 != wall_num_1))
  154.                            for (int wall_num_6=0; wall_num_6 < 6; wall_num_6++)
  155.                              if ((wall_num_6 != wall_num_5)
  156.                              &&  (wall_num_6 != wall_num_4)
  157.                              &&  (wall_num_6 != wall_num_3)
  158.                              &&  (wall_num_6 != wall_num_2)
  159.                              &&  (wall_num_6 != wall_num_1))
  160.                                {
  161.                                  wall[order_num][wall_num_6]='\0';
  162.                                  wall[order_num][wall_num_5]='\1';
  163.                                  wall[order_num][wall_num_4]='\2';
  164.                                  wall[order_num][wall_num_3]='\3';
  165.                                  wall[order_num][wall_num_2]='\4';
  166.                                  wall[order_num][wall_num_1]='\5';
  167.                                  order_num++;
  168.                                }
  169.          order_selector=new oracle(&seed[0],order_num);
  170.          row_selector=new oracle(&seed[0],num_rows);
  171.          column_selector=new oracle(&seed[0],num_columns);
  172.          int finished=FALSE;
  173.          // Generate mazes until you have one that is hard to solve.
  174.          do
  175.            {
  176.               // Pick a starting room.
  177.               first.column_num=column_selector->random_number();
  178.               if ((first.column_num)%2)
  179.                 do
  180.                   {
  181.                     first.row_num=row_selector->random_number();
  182.                   }
  183.                 while (first.row_num == (num_rows-1));
  184.               else
  185.                 first.row_num=row_selector->random_number();
  186.               current.row_num=first.row_num;
  187.               current.column_num=first.column_num;
  188.               // Excavate the starting room.
  189.               room[current.row_num][current.column_num].mark_floor(' ');
  190.               // Pick the order in which the walls of the starting room will be
  191.               // considered.
  192.               room[current.row_num][current.column_num].set_order(
  193.                order_selector->random_number());
  194.               // Excavate rooms until there are no more to excavate.
  195.               do
  196.                 {
  197.                    mud_filled_room_found=FALSE;
  198.                    // Find an adjacent room (not yet considered) that needs
  199.                    // excavating.
  200.                    do
  201.                      {
  202.                         wall_num=room[current.row_num][
  203.                          current.column_num].next_wall_num();
  204.                         if (wall_num < '\6')
  205.                           {
  206.                              wall_to_check=wall[room[current.row_num][
  207.                               current.column_num].order_to_check()][wall_num];
  208.                              if (room[current.row_num][
  209.                               current.column_num].wall_up(wall_to_check))
  210.                                {
  211.                                   next.column_num=current.column_num
  212.                                    +delta[(current.column_num)%2]
  213.                                    [wall_to_check].column_num;
  214.                                   if ((next.column_num >= 0)
  215.                                   &&  (next.column_num < num_columns))
  216.                                     {
  217.                                       next.row_num=current.row_num
  218.                                        +delta[(current.column_num)%2]
  219.                                        [wall_to_check].row_num;
  220.                                       if ((next.row_num >= 0)
  221.                                       &&  ((((next.column_num)%2 == 1)
  222.                                          && (next.row_num < (num_rows-1)))
  223.                                        ||  (((next.column_num)%2 == 0)
  224.                                          && (next.row_num < num_rows))))
  225.                                         {
  226.                                            if (room[next.row_num][
  227.                                             next.column_num].mark()
  228.                                             == 'M')
  229.                                              mud_filled_room_found=TRUE;
  230.                                         }
  231.                                     }
  232.                                }
  233.                           }
  234.                      }
  235.                    while ((wall_num < '\6')
  236.                    &&     (! mud_filled_room_found));
  237.                    if (mud_filled_room_found)
  238.                    // an adjacent room needs excavating
  239.                      {
  240.                         // Exit the current room, knocking down a wall.
  241.                         room[current.row_num][
  242.                          current.column_num].knock_down_wall(wall_to_check);
  243.                         way_out=char(((int) wall_to_check+3)%6);
  244.                         // Enter the adjacent room, knocking down a wall.
  245.                         room[next.row_num][next.column_num].knock_down_wall(
  246.                          way_out);
  247.                         // Record how to return to the previous room.
  248.                         room[next.row_num][next.column_num].set_way_out(
  249.                          way_out);
  250.                         current.row_num=next.row_num;
  251.                         current.column_num=next.column_num;
  252.                         // Excavate the room.
  253.                         room[current.row_num][current.column_num].mark_floor(
  254.                          ' ');
  255.                         // Select the order in which the walls of the room will
  256.                         // be considered.
  257.                         room[current.row_num][current.column_num].set_order(
  258.                          order_selector->random_number());
  259.                      }
  260.                    else
  261.                    // no adjacent room needs excavating
  262.                      {
  263.                         if ((first.row_num != current.row_num)
  264.                         ||  (first.column_num != current.column_num))
  265.                           {
  266.                              // Go back to the room from which you entered
  267.                              // the current room.
  268.                              next.row_num=current.row_num+delta[
  269.                               (current.column_num)%2]
  270.                               [room[current.row_num]
  271.                               [current.column_num].way_back()].row_num;
  272.                              next.column_num=current.column_num+delta[
  273.                               (current.column_num)%2]
  274.                               [room[current.row_num]
  275.                               [current.column_num].way_back()].column_num;
  276.                              current.row_num=next.row_num;
  277.                              current.column_num=next.column_num;
  278.                           }
  279.                      }
  280.                 }
  281.               while ((first.row_num != current.row_num)
  282.               ||     (first.column_num != current.column_num)
  283.               ||     (wall_num < '\6'));
  284.               if (maze_okay()) // Maze is hard to solve.
  285.                 finished=TRUE;
  286.               else             // Prepare to try another maze.
  287.                 for (int row_num=0; row_num < num_rows; row_num++)
  288.                   for (int column_num=0; column_num < num_columns; column_num++)
  289.                     room[row_num][column_num].reinitialize();
  290.            }
  291.          while (! finished);
  292.          // Knock down walls blocking the entrance and exit to the maze.
  293.          room[0][0].knock_down_wall(0);
  294.          room[num_rows-1][num_columns-1].knock_down_wall(3);
  295.  
  296.          delete column_selector;
  297.          delete row_selector;
  298.          delete order_selector;
  299.  
  300.          // Generate a 2D plot of the maze.  Each element of "page" corresponds
  301.          // to a possible position of a brick composing the maze.  An element
  302.          // has value 'W' if a brick is present and value ' ' otherwise.  Each
  303.          // wall is "wall_thickness" bricks thick.
  304.          for (y1=0; y1 < num_y_dots; y1++)
  305.            for (x1=0; x1 < num_x_dots; x1++)
  306.              page[y1][x1]=' ';
  307.          for (int row_num=0; row_num < num_rows; row_num++)
  308.            {
  309.              int half_column_num=0;
  310.              for (int column_num=0; column_num < num_columns; column_num+=2)
  311.                {
  312.                  if (room[row_num][column_num].wall_up('\0'))
  313.                    {
  314.                       x1=8*half_column_num+2;
  315.                       y1=4*row_num;
  316.                       x2=x1+2;
  317.                       y2=y1;
  318.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  319.                        wall_thickness*x2,wall_thickness*y2);
  320.                       //    ***
  321.                       //   O   O
  322.                       //  O     OOO
  323.                       //   O   O
  324.                       //    OOO
  325.                    }
  326.                  half_column_num++;
  327.                }
  328.              half_column_num=0;
  329.              for (column_num=0; column_num < num_columns; column_num+=2)
  330.                {
  331.                  if (room[row_num][column_num].wall_up('\1'))
  332.                    {
  333.                       x1=8*half_column_num;
  334.                       y1=4*row_num+2;
  335.                       x2=x1+2;
  336.                       y2=y1-2;
  337.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  338.                        wall_thickness*x2,wall_thickness*y2);
  339.                       //    *OO
  340.                       //   *   O
  341.                       //  *     OOO
  342.                       //   O   O
  343.                       //    OOO
  344.                    }
  345.                  if (room[row_num][column_num].wall_up('\5'))
  346.                    {
  347.                       x1=8*half_column_num+4;
  348.                       y1=4*row_num;
  349.                       x2=x1+2;
  350.                       y2=y1+2;
  351.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  352.                        wall_thickness*x2,wall_thickness*y2);
  353.                       //    OO*
  354.                       //   O   *
  355.                       //  O     *OO
  356.                       //   O   O
  357.                       //    OOO
  358.                    }
  359.                  half_column_num++;
  360.                }
  361.              half_column_num=0;
  362.              for (column_num=0; column_num < (num_columns-1); column_num+=2)
  363.                {
  364.                   if (row_num != (num_rows-1))
  365.                     {
  366.                       if (room[row_num][column_num+1].wall_up('\0'))
  367.                         {
  368.                            x1=8*half_column_num+6;
  369.                            y1=4*row_num+2;
  370.                            x2=x1+2;
  371.                            y2=y1;
  372.                            draw_line_on_page(wall_thickness*x1,
  373.                             wall_thickness*y1,wall_thickness*x2,
  374.                             wall_thickness*y2);
  375.                            //    OOO
  376.                            //   O   O
  377.                            //  O     ***
  378.                            //   O   O
  379.                            //    OOO
  380.                         }
  381.                     }
  382.                  half_column_num++;
  383.                }
  384.              half_column_num=0;
  385.              for (column_num=0; column_num < num_columns; column_num+=2)
  386.                {
  387.                  if (room[row_num][column_num].wall_up('\2'))
  388.                    {
  389.                       x1=8*half_column_num;
  390.                       y1=4*row_num+2;
  391.                       x2=x1+2;
  392.                       y2=y1+2;
  393.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  394.                        wall_thickness*x2,wall_thickness*y2);
  395.                       //    OOO
  396.                       //   O   O
  397.                       //  *     OOO
  398.                       //   *   O
  399.                       //    *OO
  400.                    }
  401.                  if (room[row_num][column_num].wall_up('\4'))
  402.                    {
  403.                       x1=8*half_column_num+4;
  404.                       y1=4*row_num+4;
  405.                       x2=x1+2;
  406.                       y2=y1-2;
  407.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  408.                        wall_thickness*x2,wall_thickness*y2);
  409.                       //    OOO
  410.                       //   O   O
  411.                       //  O     *OO
  412.                       //   O   *
  413.                       //    OO*
  414.                    }
  415.                  half_column_num++;
  416.                }
  417.            }
  418.          int half_column_num=0;
  419.          for (int column_num=0; column_num < num_columns; column_num+=2)
  420.            {
  421.               if (room[num_rows-1][column_num].wall_up('\3'))
  422.                 {
  423.                    x1=8*half_column_num+2;
  424.                    y1=4*(num_rows-1)+4;
  425.                    x2=x1+2;
  426.                    y2=y1;
  427.                    draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  428.                     wall_thickness*x2,wall_thickness*y2);
  429.                    //    OOO
  430.                    //   O   O
  431.                    //  O     OOO
  432.                    //   O   O
  433.                    //    ***
  434.                 }
  435.               if (column_num+1 < num_columns)
  436.                 {
  437.                    if (room[num_rows-2][column_num+1].wall_up('\3'))
  438.                      {
  439.                         x1=8*half_column_num+6;
  440.                         y1=4*(num_rows-1)+2;
  441.                         x2=x1+2;
  442.                         y2=y1;
  443.                         draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  444.                          wall_thickness*x2,wall_thickness*y2);
  445.                         //    OOO
  446.                         //   O   O
  447.                         //  O     ***
  448.                         //   O   O
  449.                         //    OOO
  450.                      }
  451.                 }
  452.              half_column_num++;
  453.            }
  454.       }
  455.   }
  456.  
  457. hexmaze::~hexmaze()
  458.   {
  459.     if (memory_allocated)
  460.       {
  461.         // Free dynamically allocated memory.
  462.         for (int y_dot_num=num_y_dots-1; y_dot_num >= 0; y_dot_num--)
  463.           delete [] page[y_dot_num];
  464.         delete [] page;
  465.         for (int row_num=num_rows-1; row_num >= 0; row_num--)
  466.           delete [] room[row_num];
  467.         delete [] room;
  468.       }
  469.   }
  470.  
  471. void hexmaze::draw_line_on_page(
  472.   int  x1,
  473.   int  y1,
  474.   int  x2,
  475.   int  y2)
  476. //      Draw wall (of bricks) on "page".
  477.     {
  478.       int error;
  479.       int error_prime_x;
  480.       int error_prime_y;
  481.       int permissible_delta_x;
  482.       int permissible_delta_y;
  483.       int x;
  484.       int x_diff;
  485.       int y;
  486.       int y_diff;
  487.  
  488.       error=0;
  489.       if (x2 >= x1)
  490.         permissible_delta_x=1;
  491.       else
  492.         permissible_delta_x=-1;
  493.       if (y2 >= y1)
  494.         permissible_delta_y=1;
  495.       else
  496.         permissible_delta_y=-1;
  497.       x=x1;
  498.       y=y1;
  499.       x_diff=x2-x1;
  500.       y_diff=y2-y1;
  501.       set_point_on_page(x,y);
  502.       while ((x != x2) || (y != y2))
  503.         {
  504.           error_prime_x=error+permissible_delta_x*y_diff;
  505.           error_prime_y=error-permissible_delta_y*x_diff;
  506.           if (abs(error_prime_x) <= abs(error_prime_y))
  507.             {
  508.               x+=permissible_delta_x;
  509.               error=error_prime_x;
  510.             }
  511.           else
  512.             {
  513.               y+=permissible_delta_y;
  514.               error=error_prime_y;
  515.             }
  516.           set_point_on_page(x,y);
  517.         }
  518.       return;
  519.     }
  520.  
  521. int hexmaze::maze_okay()
  522.   {
  523.     int  adjacency;
  524.     struct
  525.       {
  526.          int row_num;
  527.          int column_num;
  528.       }  delta [2] [6];
  529.     struct
  530.       {
  531.          int row_num;
  532.          int column_num;
  533.       }  next;
  534.     int  num_rooms_in_maze;
  535.     int  num_rooms_in_solution;
  536.     int  passage_found;
  537.     struct
  538.       {
  539.          int row_num;
  540.          int column_num;
  541.       }  previous;
  542.     int  result;
  543.     struct
  544.       {
  545.          int row_num;
  546.          int column_num;
  547.       }  saved;
  548.     char wall_to_check;
  549.     char way_out;
  550.  
  551.     // Set up the directions by which a room can be exited.
  552.     // Even columns.
  553.     delta[0][0].row_num=-1;    // north
  554.     delta[0][0].column_num=0;
  555.     delta[0][1].row_num=-1;    // northwest
  556.     delta[0][1].column_num=-1;
  557.     delta[0][2].row_num=0;     // southwest
  558.     delta[0][2].column_num=-1;
  559.     delta[0][3].row_num=1;     // south
  560.     delta[0][3].column_num=0;
  561.     delta[0][4].row_num=0;     // southeast
  562.     delta[0][4].column_num=1;
  563.     delta[0][5].row_num=-1;    // northeast
  564.     delta[0][5].column_num=1;
  565.     // Odd columns.
  566.     delta[1][0].row_num=-1;    // north
  567.     delta[1][0].column_num=0;
  568.     delta[1][1].row_num=0;     // northwest
  569.     delta[1][1].column_num=-1;
  570.     delta[1][2].row_num=1;     // southwest
  571.     delta[1][2].column_num=-1;
  572.     delta[1][3].row_num=1;     // south
  573.     delta[1][3].column_num=0;
  574.     delta[1][4].row_num=1;     // southeast
  575.     delta[1][4].column_num=1;
  576.     delta[1][5].row_num=0;     // northeast
  577.     delta[1][5].column_num=1;
  578.     // Solve the maze.
  579.  
  580.     // Start at the entrance.
  581.     current.row_num=0;
  582.     current.column_num=0;
  583.     // Mark the room as part of the solution.
  584.     room[current.row_num][current.column_num].mark_floor('S');
  585.     num_rooms_in_solution=1;
  586.     // Prepare to consider all the walls of the room.
  587.     room[current.row_num][current.column_num].zero_wall_to_check();
  588.     // Try rooms until you get to the exit.
  589.     do
  590.       {
  591.         // Find a passage (not yet considered) out of the current room leading
  592.         // to a room not part of the proposed solution.
  593.         passage_found=FALSE;
  594.         do
  595.           {
  596.             wall_to_check
  597.              =room[current.row_num][current.column_num].next_wall_num();
  598.             if (wall_to_check < '\6')
  599.               {
  600.                  if (! (room[current.row_num][
  601.                   current.column_num].wall_up(wall_to_check)))
  602.                    {
  603.                       next.column_num=current.column_num
  604.                        +delta[(current.column_num)%2]
  605.                        [wall_to_check].column_num;
  606.                       if ((next.column_num >= 0)
  607.                       &&  (next.column_num < num_columns))
  608.                         {
  609.                           next.row_num=current.row_num
  610.                            +delta[(current.column_num)%2]
  611.                            [wall_to_check].row_num;
  612.                           if ((next.row_num >= 0)
  613.                           &&  ((((next.column_num)%2 == 1)
  614.                              && (next.row_num < (num_rows-1)))
  615.                            ||  (((next.column_num)%2 == 0)
  616.                              && (next.row_num < num_rows))))
  617.                             {
  618.                                if (room[next.row_num][
  619.                                 next.column_num].mark()
  620.                                 == ' ')
  621.                                  passage_found=TRUE;
  622.                             }
  623.                         }
  624.                    }
  625.               }
  626.           }
  627.         while ((! passage_found) && (wall_to_check < '\6'));
  628.         if (passage_found)
  629.         // passage to room not currently part of proposed solution found
  630.           {
  631.             // Enter the room.
  632.             current.row_num=next.row_num;
  633.             current.column_num=next.column_num;
  634.             // Record the way back to the previous room.
  635.             way_out=char(((int) wall_to_check+3)%6);
  636.             room[current.row_num][current.column_num].set_way_out(way_out);
  637.             // Mark the room as part of the proposed solution.
  638.             room[current.row_num][current.column_num].mark_floor('S');
  639.             num_rooms_in_solution++;
  640.             // Prepare to consider all the walls of the room.
  641.             room[current.row_num][current.column_num].zero_wall_to_check();
  642.           }
  643.         else
  644.         // dead end
  645.           {
  646.             // Mark current room as not part of proposed solution.
  647.             room[current.row_num][current.column_num].mark_floor(' ');
  648.             num_rooms_in_solution--;
  649.             // Go back to the room from which this room was entered.
  650.             next.row_num=current.row_num+delta[(current.column_num)%2][
  651.              room[current.row_num][current.column_num].way_back()].row_num;
  652.             next.column_num=current.column_num+delta[(current.column_num)%2][
  653.              room[current.row_num][current.column_num].way_back()].column_num;
  654.             current.row_num=next.row_num;
  655.             current.column_num=next.column_num;
  656.           }
  657.       }
  658.     while((current.row_num != num_rows-1)
  659.     ||    (current.column_num != num_columns-1));
  660.  
  661.     // Now that the maze is solved, calculate the number of rooms in the
  662.     // solution (or outside the maze) that are adjacent to the rooms in
  663.     // the solution.
  664.     adjacency=0;
  665.     previous.row_num=-1;
  666.     previous.column_num=0;
  667.     current.row_num=0;
  668.     current.column_num=0;
  669.     do
  670.       {
  671.         for (wall_to_check='\0'; wall_to_check < '\6'; wall_to_check++)
  672.           if (room[current.row_num][current.column_num].wall_up(wall_to_check))
  673.             {
  674.                next.column_num=current.column_num
  675.                 +delta[(current.column_num)%2]
  676.                 [wall_to_check].column_num;
  677.                if ((next.column_num >= 0)
  678.                &&  (next.column_num < num_columns))
  679.                  {
  680.                    next.row_num=current.row_num
  681.                     +delta[(current.column_num)%2]
  682.                     [wall_to_check].row_num;
  683.                    if ((next.row_num >= 0)
  684.                    &&  ((((next.column_num)%2 == 1)
  685.                       && (next.row_num < (num_rows-1)))
  686.                     ||  (((next.column_num)%2 == 0)
  687.                       && (next.row_num < num_rows))))
  688.                      {
  689.                         if (room[next.row_num][next.column_num].mark() == 'S')
  690.                           adjacency++;
  691.                      }
  692.                    else
  693.                      adjacency++;
  694.                  }
  695.                else
  696.                  adjacency++;
  697.             }
  698.           else
  699.             {
  700.                next.column_num=current.column_num
  701.                 +delta[(current.column_num)%2]
  702.                 [wall_to_check].column_num;
  703.                if ((next.column_num >= 0)
  704.                &&  (next.column_num < num_columns))
  705.                  {
  706.                    next.row_num=current.row_num
  707.                     +delta[(current.column_num)%2]
  708.                     [wall_to_check].row_num;
  709.                    if ((next.row_num >= 0)
  710.                    &&  ((((next.column_num)%2 == 1)
  711.                       && (next.row_num < (num_rows-1)))
  712.                     ||  (((next.column_num)%2 == 0)
  713.                       && (next.row_num < num_rows))))
  714.                      {
  715.                         if ((room[next.row_num][next.column_num].mark() == 'S')
  716.                         &&  ((previous.row_num != next.row_num)
  717.                           || (previous.column_num != next.column_num)))
  718.                           {
  719.                             saved.row_num=next.row_num;
  720.                             saved.column_num=next.column_num;
  721.                           }
  722.                      }
  723.                  }
  724.             }
  725.         previous.row_num=current.row_num;
  726.         previous.column_num=current.column_num;
  727.         current.row_num=saved.row_num;
  728.         current.column_num=saved.column_num;
  729.       }
  730.     while((current.row_num != num_rows-1)
  731.     ||    (current.column_num != num_columns-1));
  732.     for (wall_to_check='\0'; wall_to_check < '\6'; wall_to_check++)
  733.       if (room[current.row_num][current.column_num].wall_up(wall_to_check))
  734.         {
  735.            next.column_num=current.column_num
  736.             +delta[(current.column_num)%2]
  737.             [wall_to_check].column_num;
  738.            if ((next.column_num >= 0)
  739.            &&  (next.column_num < num_columns))
  740.              {
  741.                 next.row_num=current.row_num
  742.                  +delta[(current.column_num)%2]
  743.                  [wall_to_check].row_num;
  744.                 if ((next.row_num >= 0)
  745.                 &&  ((((next.column_num)%2 == 1)
  746.                    && (next.row_num < (num_rows-1)))
  747.                  ||  (((next.column_num)%2 == 0)
  748.                    && (next.row_num < num_rows))))
  749.                   {
  750.                      if (room[next.row_num][next.column_num].mark() == 'S')
  751.                        adjacency++;
  752.                   }
  753.                 else
  754.                   adjacency++;
  755.              }
  756.            else
  757.              adjacency++;
  758.         }
  759.     num_rooms_in_maze=num_rows*num_columns-(num_columns/2);
  760.  
  761.     // The maze is hard to solve (from the outside) if more than a third of its
  762.     // rooms are part of its solution and rooms not part of its solution tend to
  763.     // be next to rooms in its solution.
  764.     if ((3*num_rooms_in_solution >= num_rooms_in_maze)
  765.     &&  (5*adjacency <= 11*num_rooms_in_solution))
  766.       result=TRUE;
  767.     else
  768.       result=FALSE;
  769.     return result;
  770.   }
  771.  
  772. int hexmaze::external_to_maze(double x,double y)
  773. //      Return TRUE if and only if a point (x,y) is external to the maze.
  774.   {
  775.     int result;
  776.     int x_out;
  777.     int x_next;
  778.     int y_out;
  779.     int y_next;
  780.  
  781.     result=FALSE;
  782.     y_out=(int) x;
  783.     if (y_out < 0)
  784.       result=TRUE;
  785.     else
  786.       if (y_out > y_dot_max)
  787.         result=TRUE;
  788.       else
  789.         {
  790.           x_out=(int) y;
  791.           if (x_out < 0)
  792.             result=TRUE;
  793.           else
  794.             if (x_out > x_dot_max)
  795.               result=TRUE;
  796.             else
  797.               // A point is external to the maze if you don't have to cross
  798.               // a wall, the entrance, or the exit to move from the point to
  799.               // outside the maze.
  800.               {
  801.                 if ((x_out/wall_thickness != 3)
  802.                 &&  (x_out/wall_thickness != max_x-3))
  803.                   {
  804.                     x_next=x_out;
  805.                     result=TRUE;
  806.                     while((result) && (x_next >= 0))
  807.                       {
  808.                         if (page[y_out][x_next] == ' ')
  809.                           x_next--;
  810.                         else
  811.                           result=FALSE;
  812.                       }
  813.                     if (! result)
  814.                       {
  815.                         x_next=x_out;
  816.                         result=TRUE;
  817.                         while((result) && (x_next <= x_dot_max))
  818.                           {
  819.                             if (page[y_out][x_next] == ' ')
  820.                               x_next++;
  821.                             else
  822.                               result=FALSE;
  823.                           }
  824.                       }
  825.                     if (! result)
  826.                       {
  827.                         y_next=y_out;
  828.                         result=TRUE;
  829.                         while((result) && (y_next >= 0))
  830.                           {
  831.                             if (page[y_next][x_out] == ' ')
  832.                               y_next--;
  833.                             else
  834.                               result=FALSE;
  835.                           }
  836.                       }
  837.                     if (! result)
  838.                       {
  839.                         y_next=y_out;
  840.                         result=TRUE;
  841.                         while((result) && (y_next <= y_dot_max))
  842.                           {
  843.                             if (page[y_next][x_out] == ' ')
  844.                               y_next++;
  845.                             else
  846.                               result=FALSE;
  847.                           }
  848.                       }
  849.                   }
  850.               }
  851.         }
  852.     return result;
  853.   }
  854.  
  855. double hexmaze::f(double x,double y)
  856. //      Return 5.0*wall_thickness if a point (x,y) is on a wall, 0.0 otherwise.
  857.   {
  858.     int    x_out;
  859.     int    y_out;
  860.     double z;
  861.  
  862.     y_out=(int) x;
  863.     if (y_out < 0)
  864.       z=0.0;
  865.     else
  866.       if (y_out > y_dot_max)
  867.         z=0.0;
  868.       else
  869.         {
  870.           x_out=(int) y;
  871.           if (x_out < 0)
  872.             z=0.0;
  873.           else
  874.             if (x_out > x_dot_max)
  875.               z=0.0;
  876.             else
  877.               if (page[y_out][x_out] == 'W')
  878.                 z=1.0;
  879.               else
  880.                 z=0.0;
  881.         }
  882.     return z*double(5*wall_thickness);
  883.   }
  884.  
  885. int hexmaze::part_of_solution(double x,double y)
  886. //      Return TRUE if and only if a point (x,y) is on a wall outlining the
  887. // solution to the maze.
  888.   {
  889.     int base_x;
  890.     int base_x_mod_8;
  891.     int base_y;
  892.     int base_y_mod_4;
  893.     int half_column_num;
  894.     int result;
  895.     int row_num;
  896.     int x_out;
  897.     int y_out;
  898.  
  899.     y_out=(int) x;
  900.     if (y_out < 0)
  901.       result=FALSE;
  902.     else
  903.       if (y_out > y_dot_max)
  904.         result=FALSE;
  905.       else
  906.         {
  907.           x_out=(int) y;
  908.           if (x_out < 0)
  909.             result=FALSE;
  910.           else
  911.             if (x_out > x_dot_max)
  912.               result=FALSE;
  913.             else
  914.               if (page[y_out][x_out] == 'W')
  915.                 {
  916.                   result=FALSE;
  917.                   base_x=x_out/wall_thickness;
  918.                   half_column_num=base_x/8;
  919.                   base_x_mod_8=base_x-8*half_column_num;
  920.                   base_y=y_out/wall_thickness;
  921.                   row_num=base_y/4;
  922.                   base_y_mod_4=base_y-4*row_num;
  923.                   switch (base_y_mod_4)
  924.                   //      000
  925.                   //     1   1
  926.                   //    2     22 
  927.                   //     3   3
  928.                   //      000
  929.                     {
  930.                       case 0:
  931.                         if (base_x_mod_8 < 3)
  932.                         //      *00
  933.                         //     1   1
  934.                         //    2     22
  935.                         //     3   3
  936.                         //      000
  937.                           {
  938.                             if (row_num < num_rows)
  939.                               {
  940.                                 if (room[row_num][2*half_column_num].mark()
  941.                                  == 'S')
  942.                                   result=TRUE;
  943.                               }
  944.                             if (! result)
  945.                               {
  946.                                 if (row_num > 0)
  947.                                   {
  948.                                     if (room[row_num-1]
  949.                                      [2*half_column_num].mark() == 'S')
  950.                                       result=TRUE;
  951.                                   }
  952.                               }
  953.                             if (! result)
  954.                               {
  955.                                 if (row_num > 0)
  956.                                   {
  957.                                     if (half_column_num > 0)
  958.                                       {
  959.                                         if (room[row_num-1]
  960.                                          [2*half_column_num-1].mark() == 'S')
  961.                                           result=TRUE;
  962.                                       }
  963.                                   }
  964.                               }
  965.                           }
  966.                         else
  967.                           if (base_x_mod_8 > 3)
  968.                           //      00*
  969.                           //     1   1
  970.                           //    2     22
  971.                           //     3   3
  972.                           //      000
  973.                             {
  974.                               if (row_num < num_rows)
  975.                                 {
  976.                                   if (room[row_num][2*half_column_num].mark()
  977.                                    == 'S')
  978.                                     result=TRUE;
  979.                                 }
  980.                               if (! result)
  981.                                 {
  982.                                   if (row_num > 0)
  983.                                     {
  984.                                       if (room[row_num-1]
  985.                                        [2*half_column_num].mark() == 'S')
  986.                                         result=TRUE;
  987.                                     }
  988.                                 }
  989.                               if (! result)
  990.                                 {
  991.                                   if (row_num > 0)
  992.                                     {
  993.                                       if (2*half_column_num+1 < num_columns)
  994.                                         {
  995.                                           if ((row_num-1) < (num_rows-1))
  996.                                             {
  997.                                               if (room[row_num-1]
  998.                                                [2*half_column_num+1].mark()
  999.                                                == 'S')
  1000.                                                 result=TRUE;
  1001.                                             }
  1002.                                         }
  1003.                                     }
  1004.                                 }
  1005.                             }
  1006.                           else
  1007.                           //      0*0
  1008.                           //     1   1
  1009.                           //    2     22
  1010.                           //     3   3
  1011.                           //      000
  1012.                             {
  1013.                               if (row_num < num_rows)
  1014.                                 {
  1015.                                   if (room[row_num][2*half_column_num].mark()
  1016.                                    == 'S')
  1017.                                     result=TRUE;
  1018.                                 }
  1019.                               if (! result)
  1020.                                 {
  1021.                                   if (row_num > 0)
  1022.                                     {
  1023.                                       if (room[row_num-1]
  1024.                                        [2*half_column_num].mark() == 'S')
  1025.                                         result=TRUE;
  1026.                                     }
  1027.                                 }
  1028.                             }
  1029.                         break;
  1030.                       case 1:
  1031.                         if (base_x_mod_8 < 3)
  1032.                         //      000
  1033.                         //     *   1
  1034.                         //    2     22
  1035.                         //     3   3
  1036.                         //      000
  1037.                           {
  1038.                             if (room[row_num][2*half_column_num].mark() == 'S')
  1039.                               result=TRUE;
  1040.                             if (! result)
  1041.                               {
  1042.                                 if (row_num > 0)
  1043.                                   {
  1044.                                     if (half_column_num > 0)
  1045.                                       {
  1046.                                         if (room[row_num-1]
  1047.                                          [2*half_column_num-1].mark() == 'S')
  1048.                                           result=TRUE;
  1049.                                       }
  1050.                                   }
  1051.                               }
  1052.                           }
  1053.                         else
  1054.                         //      000
  1055.                         //     1   *
  1056.                         //    2     22
  1057.                         //     3   3
  1058.                         //      000
  1059.                           {
  1060.                             if (room[row_num][2*half_column_num].mark() == 'S')
  1061.                               result=TRUE;
  1062.                             if (! result)
  1063.                               {
  1064.                                 if (row_num > 0)
  1065.                                   {
  1066.                                     if (2*half_column_num+1 < num_columns)
  1067.                                       {
  1068.                                         if (room[row_num-1]
  1069.                                          [2*half_column_num+1].mark() == 'S')
  1070.                                           result=TRUE;
  1071.                                       }
  1072.                                   }
  1073.                               }
  1074.                           }
  1075.                         break;
  1076.                       case 2:
  1077.                         if (base_x_mod_8 < 3)
  1078.                         //      000
  1079.                         //     1   1
  1080.                         //    *     22
  1081.                         //     3   3
  1082.                         //      000
  1083.                           {
  1084.                             if (room[row_num][2*half_column_num].mark() == 'S')
  1085.                               result=TRUE;
  1086.                             else
  1087.                               {
  1088.                                 if (half_column_num > 0)
  1089.                                   {
  1090.                                     if (row_num > 0)
  1091.                                       {
  1092.                                         if (room[row_num-1]
  1093.                                          [2*half_column_num-1].mark() == 'S')
  1094.                                           result=TRUE;
  1095.                                       }
  1096.                                     if (! result)
  1097.                                       {
  1098.                                         if (row_num < (num_rows-1))
  1099.                                           {
  1100.                                             if (room[row_num]
  1101.                                              [2*half_column_num-1].mark()
  1102.                                              == 'S')
  1103.                                               result=TRUE;
  1104.                                           }
  1105.                                       }
  1106.                                   }
  1107.                               }
  1108.                           }
  1109.                         else
  1110.                           if (base_x_mod_8 < 7) // case 6
  1111.                           //      000
  1112.                           //     1   1
  1113.                           //    2     *2
  1114.                           //     3   3
  1115.                           //      000
  1116.                             {
  1117.                               if (room[row_num][2*half_column_num].mark()
  1118.                                == 'S')
  1119.                                 result=TRUE;
  1120.                               if (! result)
  1121.                                 {
  1122.                                   if (row_num < num_rows-1)
  1123.                                     {
  1124.                                       if (2*half_column_num+1 < num_columns)
  1125.                                         {
  1126.                                           if (room[row_num]
  1127.                                            [2*half_column_num+1].mark() == 'S')
  1128.                                             result=TRUE;
  1129.                                         }
  1130.                                     }
  1131.                                 }
  1132.                               if (! result)
  1133.                                 {
  1134.                                   if (row_num > 0)
  1135.                                     {
  1136.                                       if (2*half_column_num+1 < num_columns)
  1137.                                         {
  1138.                                           if (room[row_num-1]
  1139.                                            [2*half_column_num+1].mark() == 'S')
  1140.                                             result=TRUE;
  1141.                                         }
  1142.                                     }
  1143.                                 }
  1144.                             }
  1145.                           else
  1146.                           //      000
  1147.                           //     1   1
  1148.                           //    2     2*
  1149.                           //     3   3
  1150.                           //      000
  1151.                             {
  1152.                               if (row_num < (num_rows-1))
  1153.                                 {
  1154.                                   if (room[row_num][2*half_column_num+1].mark()
  1155.                                    == 'S')
  1156.                                     result=TRUE;
  1157.                                 }
  1158.                               if (! result)
  1159.                                 {
  1160.                                   if (row_num > 0)
  1161.                                     {
  1162.                                       if (room[row_num-1]
  1163.                                        [2*half_column_num+1].mark() == 'S')
  1164.                                         result=TRUE;
  1165.                                     }
  1166.                                 }
  1167.                             }
  1168.                         break;
  1169.                       default:
  1170.                         if (base_x_mod_8 < 3)
  1171.                         //      000
  1172.                         //     1   1
  1173.                         //    2     22
  1174.                         //     *   3
  1175.                         //      000
  1176.                           {
  1177.                             if (room[row_num][2*half_column_num].mark()
  1178.                              == 'S')
  1179.                               result=TRUE;
  1180.                             else
  1181.                               {
  1182.                                 if (half_column_num > 0)
  1183.                                   {
  1184.                                     if (row_num < (num_rows-1))
  1185.                                       {
  1186.                                         if (room[row_num]
  1187.                                          [2*half_column_num-1].mark() == 'S')
  1188.                                           result=TRUE;
  1189.                                       }
  1190.                                   }
  1191.                               }
  1192.                           }
  1193.                         else
  1194.                         //      000
  1195.                         //     1   1
  1196.                         //    2     22
  1197.                         //     3   *
  1198.                         //      000
  1199.                           {
  1200.                             if (room[row_num][2*half_column_num].mark()
  1201.                              == 'S')
  1202.                               result=TRUE;
  1203.                             if (! result)
  1204.                               {
  1205.                                 if (row_num < (num_rows-1))
  1206.                                   {
  1207.                                     if (2*half_column_num+1 < num_columns)
  1208.                                       {
  1209.                                         if (room[row_num]
  1210.                                          [2*half_column_num+1].mark()
  1211.                                          == 'S')
  1212.                                           result=TRUE;
  1213.                                       }
  1214.                                   }
  1215.                               }
  1216.                           }
  1217.                         break;
  1218.                     }
  1219.                 }
  1220.               else
  1221.                 result=FALSE;
  1222.         }
  1223.     return result;
  1224.   }
  1225.  
  1226. void hexmaze::set_point_on_page(
  1227.   int  x,
  1228.   int  y)
  1229. //      Place a section of wall on "page".  Each section is "wall_thickness"
  1230. // bricks long and "wall_thickness" bricks wide.
  1231.     {
  1232.       int x_offset;
  1233.       int x_out;
  1234.       int y_offset;
  1235.       int y_out;
  1236.  
  1237.       for (x_offset=0; x_offset < wall_thickness; x_offset++)
  1238.         {
  1239.           x_out=x+x_offset;
  1240.           for (y_offset=0; y_offset < wall_thickness; y_offset++)
  1241.             {
  1242.               y_out=y+y_offset;
  1243.               page[y_out][x_out]='W';
  1244.             }
  1245.         }
  1246.       return;
  1247.     }
  1248.